//
//  BSTTree.hpp
//  DataStructureC++
//
//  Created by zhangbaochuan on 2020/4/11.
//  Copyright © 2020 Geex. All rights reserved.
//

#ifndef BSTTree_hpp
#define BSTTree_hpp

#include <stdio.h>
#include <iostream>
#include <queue>
#include <sstream>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <cstddef>
#include <iostream>
#include <fstream>
#include <cassert>
#include <ctime>


template <typename Key, typename Value>
class BST {
public:
    struct Node {
        Key key;
        Value value;
        Node *left;
        Node *right;
        
        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }
    };
    Node *root;
    int count;
    
    Node *BSTInsert(Node *node, Key key, Value value) {
        if (node == NULL) {
            return new Node(key, value);
        }
        
        if (node->key == key) {
            node->value = value;
        } else if (node->key > key) {
            node->left = BSTInsert(node->left, key, value);
        } else {
            node->right = BSTInsert(node->right, key, value);
        }
        return node;
    }
    
    
    void destroy(Node *node) {
        if (node != NULL) {
            destroy(node->left);
            destroy(node->right);
            delete node;
            count--;
        }
    }
    
    Node *createNode(Key key, Value value) {
        return new Node(key, value);
    }
    
    BST() {
        root = NULL;
        count = 0;
    }
    
    ~BST() {
        destroy(root);
    }
    
    void insert(Key key, Value value) {
        count ++;
        root = BSTInsert(root, key, value);
        
    }
#pragma mark -- 是否包含
    bool BstContain(Node *node, Key key, Value value) {
        if (node == NULL) {
            return false;
        }
        
        if (node->key == key) {
            return true;
        } else if (node->key > key) {
            return BstContain(node->left, key, value);
        } else {
            return BstContain(node->right, key, value);
        }
        
    }
    
    void isBstcontain(int num) {
        std::cout << BstContain(root, num, 1) << " 是否包含";
    }
#pragma mark -- 是否找到该节点 并返回
    Node *BstSearch(Node *node, Key key) {
        if (node == NULL) {
            return NULL;
        }
        
        if (node->key == key) {
            return node;
        } else if(node->key > key) {
            return BstSearch(node->left, key);
        } else {
            return BstSearch(node->right, key);
        }
    }
    
    void isSearchNode(int num) {
        Node *node = BstSearch(root, num);
        Node *nodeleft = node->left;
        Node *nodeRight = node->right;
        
        int left =  nodeleft == NULL ? -1 : nodeleft->key;
        int right = nodeRight == NULL ? -1 : nodeRight->key;
        std::cout << "\n" << node->key << " == key";
        std::cout << "\n" << left  << " == left";
        std::cout << "\n" << right << " == right";
    }
# pragma mark -- 前序遍历
    void proOrder(Node *node) {
        if(node != NULL) {
            std::cout << node->key << "    ";
            proOrder(node->left);
            proOrder(node->right);
        }
    }
    
    void testProOrder() {
        std::cout << "\n"<< "前序遍历结果";
        proOrder(root);
    }
    
# pragma mark -- 中序p遍历
    void midOrder(Node *node) {
        
        if (node != NULL) {
            midOrder(node->left);
            std::cout << node->key << "    ";
            midOrder(node->right);
        }
    }
    
    void testMidOrder () {
        std::cout << "\n"<< "中序遍历结果";
        midOrder(root);
    }
    
#pragma mark --后续遍历
    void backOrder(Node *node) {
        if (node != NULL) {
            backOrder(node->left);
            backOrder(node->right);
            std::cout << node->key << "    ";
        }
    }
    
    void testBackOrder () {
        std::cout << "\n"<< "后序遍历结果";
        backOrder(root);
    }
    
#pragma mark --层次遍历（广度优先遍历）
    void leverOrder() {
        std::cout << "\n"<< "广度优先遍历：";
        
        std::queue<Node *> q;
        q.push(root);
        
        while (!q.empty()) {
            Node *node = q.front();
            std::cout << node->key << "    ";
            q.pop();
            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
    }
    
#pragma mark -- 最小节点
    Node *miniNum (Node *node) {
        
        if (node->left == NULL) {
            return node;
        }
        return miniNum(node->left);
        
    }
    
    void testMiniNum () {
        std::cout << "\n"<< "最小节点";
        Node *node = miniNum(root);
        std::cout << node->key << "\n";
    }
    
#pragma mark - 最大节点
    Node *maxNum(Node *node) {
        if(node->right == NULL) {
            return node;
        }
        
        return maxNum(node->right);
    }
    
    void testMaxNum() {
        std::cout << "\n"<< "最大节点";
        Node *node = maxNum(root);
        std::cout << node->key << "\n";
    }
    
#pragma mark --移除最小节点
    Node *removeMinNum (Node *node) {
        if (node->left == NULL) {
            Node *rightNode = node->right;
            delete node;
            count--;
            return rightNode;
        }
        
        node->left = removeMinNum(node->left);
        return node;
        
    }
    
    void testRemoveMinNode () {
        std::cout << "\n"<< "移除最小节点";
        removeMinNum(root);
       
    }
    
#pragma mark --移除最大节点
    Node *removeMaxNum(Node *node) {
        if (node->right == NULL) {
            Node *leftNode = node->left;
            delete node;
            count--;
            return leftNode;
        }
        
        node->right = removeMaxNum(node->right);
        return node;
    }
    
    void testRemoveMaxNode() {
        std::cout << "\n"<< "移除最大节点";
        removeMaxNum(root);
    }
        
# pragma mark --删除某个节点
    Node *removeNode(Node *node, Key key) {
        if (node == NULL) {
            return NULL;
        }
        
        if (node->key > key) {
            node->left = removeNode(node->left, key);
            return node;
        } else if (node->key < key) {
            node->right = removeNode(node->right, key);
            return node;
        } else {
            if (node->left == NULL) {
                Node *rightNode = node->right;
                delete node;
                count--;
                return rightNode;
            }
            
            if (node->right == NULL) {
                Node *leftNode = node->left;
                delete node;
                count--;
                return leftNode;
            }
            
            Node *rightMin = miniNum(node->right);
            
            Node *newNode = new Node(rightMin->key, rightMin->value);
            count++;
            newNode->right = removeMinNum(node->right);
            newNode->left = node->left;
            
            delete node;
            count--;
            return newNode;
        }
    }
    
    void testRemoveNode(Key key) {
         std::cout << "\n"<< "移除某个节点";
        removeNode(root, key);
    }
    
#pragma mark -- 前驱
    Node *predecessorFromAncestory(Node *node, Key key) {
        if (node->key == key) {
            return NULL;
        }
        
        if (key < node->key) {
            return predecessorFromAncestory(node->left, key);
        } else {
            Node *tempNode = predecessorFromAncestory(node->right, key);
            if (tempNode) {
                return tempNode;
            }
            return node;
        }
    }
    
    void testPredecessorFromAncesstory(Key key) {
        std::cout << "\n"<< "某个节点的前驱";
        Node *node = predecessorFromAncestory(root, key);
        std::cout << node->key << "\n";
    }
    
#pragma mark -- 后继
    Node *successorFromAncestor(Node *node, Key key) {
        if (node->key == key) {
            return NULL;
        }
        
        if (key > node->key) {
            return successorFromAncestor(node->right, key);
        } else {
//            assert(key < node->key);
            Node *tempNode = successorFromAncestor(node->left, key);
            if (tempNode) {
                return tempNode;
            }
            return node;
            
        }
    }
    
# pragma mark -- 打印
        
    void bstPrint(std::string name, int *arr) {
        std::string dotPath = CURRENT_PATH;
        std::string dotStr = "\ndigraph heap {\nnode[shape=circle];\nnodesep=0.3;\n";
        std::queue<Node *> q;
        q.push(root);
        int i = 0;
        while (!q.empty()) {
            Node *node = q.front();
            q.pop();
            
            if (node->left) {
                q.push(node->left);
                std::stringstream fmt;
                fmt << "\t" << node->key << "->" << node->left->key << ";\n";
                dotStr.append(fmt.str());
            } else {
                if (node->right != NULL) {
                    int sa = arr[i++];
                    std::stringstream fmt;
                    fmt << "\t" << node->key << "->" << "n" << sa << ";\n";
                    dotStr.append(fmt.str());
                }
            }
            
            if (node->right) {
                q.push(node->right);
                std::stringstream fmt;
                fmt << "\t" << node->key << "->" << node->right->key << ";\n";
                dotStr.append(fmt.str());
            } else {
                if (node->left != NULL) {
                    int sa = arr[i++];
                    std::stringstream fmt;
                    fmt << "\t" << node->key << "->" << "n" << sa << ";\n";
                    dotStr.append(fmt.str());
                }
            }
        }
        
        dotStr.append("}\n");
        
        std::cout << dotStr << std::endl;
        const char *path = dotPath.c_str();
        if(NULL == opendir(path)) {
           mkdir(path,0775);
        }
        std::stringstream fmt;
        fmt << dotPath << "/" << name <<".dot";
        const char *filePath = fmt.str().c_str();
        std::ofstream mcfile; //创建个对象
        mcfile.open(filePath,std::ios::out); //创建文件
        mcfile << dotStr;  //写入内容
        mcfile.close(); //关闭
        
        std::stringstream shell;
        shell << "cd " <<"\"" << dotPath << "\"" << " && /usr/local/bin/dot -Tpng " << name <<".dot "<< "-o "<< name <<".png ";
        system(shell.str().c_str());
    }
    
    
};

void testBSTObject1(std::string str);


#endif /* BSTTree_hpp */
